home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / archiver / lzhsourc.lzh / LZH.SRC / HUF.C < prev    next >
C/C++ Source or Header  |  1992-07-02  |  18KB  |  755 lines
  1. /**************************************************************
  2.     lzhuf.c
  3.     written by Haruyasu Yoshizaki 11/20/1988
  4.     some minor changes 4/6/1989
  5.     comments translated by Haruhiko Okumura 4/7/1989
  6.  
  7.     reinserted with modifications into 'lharc.c'
  8.     by J. Moeller 1/30/1990
  9. **************************************************************/
  10.  
  11. #define _hufst_
  12. #ifdef _hufst_
  13.   #define from extern
  14. #else
  15.   #define from
  16. #endif
  17. #ifndef __TOS__
  18. #error Please try assembling 'lzhuf.asm'!
  19. #endif
  20.  
  21. #include <stdio.h>
  22. #include <stdlib.h>
  23. #include <string.h>
  24. #include <ctype.h>
  25.  
  26. #define RDERR        13
  27. #define WTERR        14
  28. #define MAXBLK        64
  29.  
  30. extern FILE *infile, *outfile;
  31. extern char *infname, *outfname;
  32. extern long textsize, codesize;
  33. extern unsigned crc, crctbl [];
  34. extern unsigned blkcnt;
  35. extern unsigned char flg_n;
  36. extern long blocksize;
  37.  
  38. extern void error (int errcode, char *p);
  39.  
  40. #define setcrc(ch) (crc = (crc >> 8) ^ crctbl [(crc ^ (ch)) & 0xff])
  41. #ifndef _hufst_
  42. int crc_getc (register FILE *stream)
  43. {
  44.     register int ch;
  45.  
  46.     if ((ch = getc (stream)) != EOF)
  47.         setcrc (ch);
  48.  
  49.     return ch;
  50. }
  51. #else
  52.  extern int crc_getc(register FILE *stream);
  53. #endif
  54.  
  55. /********** LZSS compression **********/
  56.  
  57. #define N        4096    /* buffer size */
  58. #define F        60    /* lookahead buffer size */
  59. #define THRESHOLD    2
  60. #define NIL    N    /* leaf of tree */
  61. #define FOLD        18   /* upper limit for match_length */
  62.  
  63. from unsigned char     text_buf[N + F - 1];
  64. from int         match_position, match_length,
  65.              lson[N + 1], rson[N + 257], dad[N + 1];
  66.  
  67. void InitTree(void)  /* initialize trees */
  68. {
  69. register    int  i, *rsonp, *dadp;
  70.  
  71.     rsonp=&rson[N+1];
  72.     for (i = N + 1; i <= N + 256; i++)
  73.         *rsonp++ = 2*NIL;           /* root */
  74.     dadp=dad;
  75.     for (i = 0; i < N; i++)
  76.         *dadp++ = 2*NIL;           /* node */
  77. }
  78.  
  79. #ifndef _hufst_
  80. void InsertNode(int r)    /* insert to tree */
  81. {
  82. register    int  i, p, cmp;
  83.     unsigned char  *key;
  84.     unsigned c;
  85.  
  86.     cmp = 1;
  87.     key = &text_buf[r];
  88.     p = N + 1 + key[0];
  89.     rson[r] = lson[r] = NIL;
  90.     match_length = 0;
  91.     for ( ; ; ) {
  92.         if (cmp >= 0) {
  93.             if (rson[p] != NIL)
  94.                 p = rson[p];
  95.             else {
  96.                 rson[p] = r;
  97.                 dad[r] = p;
  98.                 return;
  99.             }
  100.         } else {
  101.             if (lson[p] != NIL)
  102.                 p = lson[p];
  103.             else {
  104.                 lson[p] = r;
  105.                 dad[r] = p;
  106.                 return;
  107.             }
  108.         }
  109.         for (i = 1; i < F; i++)
  110.             if ((cmp = key[i] - text_buf[p + i]) != 0)
  111.                 break;
  112.         if (i > THRESHOLD) {
  113.             if (i > match_length) {
  114.                 match_position = ((r - p) & (N - 1)) - 1;
  115.                 if ((match_length = i) >= F)
  116.                     break;
  117.             }
  118.             if (i == match_length) {
  119.                 if ((c = ((r - p) & (N - 1)) - 1) < match_position) {
  120.                     match_position = c;
  121.                 }
  122.             }
  123.         }
  124.     }
  125.     dad[r] = dad[p];
  126.     lson[r] = lson[p];
  127.     rson[r] = rson[p];
  128.     dad[lson[p]] = r;
  129.     dad[rson[p]] = r;
  130.     if (rson[dad[p]] == p)
  131.         rson[dad[p]] = r;
  132.     else
  133.         lson[dad[p]] = r;
  134.     dad[p] = NIL;  /* remove p */
  135. }
  136.  
  137. void DeleteNode(int p)    /* remove from tree */
  138. {
  139. register    int  q;
  140.  
  141.     if (dad[p] == NIL)
  142.         return;         /* not registered */
  143.     if (rson[p] == NIL)
  144.         q = lson[p];
  145.     else
  146.     if (lson[p] == NIL)
  147.         q = rson[p];
  148.     else {
  149.         q = lson[p];
  150.         if (rson[q] != NIL) {
  151.             do {
  152.                 q = rson[q];
  153.             } while (rson[q] != NIL);
  154.             rson[dad[q]] = lson[q];
  155.             dad[lson[q]] = dad[q];
  156.             lson[q] = lson[p];
  157.             dad[lson[p]] = q;
  158.         }
  159.         rson[q] = rson[p];
  160.         dad[rson[p]] = q;
  161.     }
  162.     dad[q] = dad[p];
  163.     if (rson[dad[p]] == p)
  164.         rson[dad[p]] = q;
  165.     else
  166.         lson[dad[p]] = q;
  167.     dad[p] = NIL;
  168. }
  169. #else
  170.   extern void DeleteNode(int p);
  171. #endif
  172. /* Huffman coding */
  173.  
  174. #define N_CHAR        (256 - THRESHOLD + F)
  175.                 /* kinds of characters (character code = 0..N_CHAR-1) */
  176. #define T        (N_CHAR * 2 - 1)    /* size of table */
  177. #define R        (T - 1)         /* position of root */
  178. #define MAX_FREQ    0x8000        /* updates tree when the */
  179.                     /* root frequency comes to this value. */
  180. typedef unsigned char uchar;
  181.  
  182.  
  183. /* table for encoding and decoding the upper 6 bits of position */
  184.  
  185. /* for encoding */
  186. uchar p_len[64] = {
  187.     0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
  188.     0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
  189.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  190.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  191.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  192.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  193.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  194.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
  195. };
  196.  
  197. uchar p_code[64] = {
  198.     0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
  199.     0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
  200.     0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
  201.     0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
  202.     0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
  203.     0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
  204.     0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
  205.     0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
  206. };
  207.  
  208. /* for decoding */
  209. uchar d_code[256] = {
  210.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  211.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  212.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  213.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  214.     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  215.     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  216.     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  217.     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  218.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  219.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  220.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  221.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  222.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  223.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  224.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  225.     0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
  226.     0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
  227.     0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
  228.     0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
  229.     0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
  230.     0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
  231.     0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
  232.     0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
  233.     0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
  234.     0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
  235.     0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
  236.     0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
  237.     0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
  238.     0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
  239.     0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
  240.     0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
  241.     0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
  242. };
  243.  
  244. uchar d_len[256] = {
  245.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  246.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  247.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  248.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  249.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  250.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  251.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  252.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  253.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  254.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  255.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  256.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  257.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  258.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  259.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  260.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  261.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  262.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  263.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  264.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  265.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  266.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  267.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  268.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  269.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  270.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  271.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  272.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  273.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  274.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  275.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  276.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  277. };
  278.  
  279.  
  280.  
  281. from unsigned freq[T + 1];   /* frequency table */
  282.  
  283. from int prnt[T + N_CHAR];   /* pointers to pare